package leetcode.code0086;

import leetcode.helper.tree.ListNode;

public class Solution86 {
	public ListNode partition(ListNode head, int x) {
		ListNode pl = new ListNode();
		ListNode ans = pl;
		ListNode pr = new ListNode();
		ListNode tail = pr;
		while (head != null) {
			if (head.val < x) {
				pl.next = head;
				pl = pl.next;
			} else {
				pr.next = head;
				pr = pr.next;
			}
			head = head.next;
		}
		pl.next = tail.next;
		pr.next = null;
		return ans.next;
	}
}
